import java.util.*;

public class Solution {


    public boolean containsNearbyDuplicate(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            //有这个元素就比比较
            if (map.containsKey(nums[i])) {
                int j = map.get(nums[i]);
                if (Math.abs(j - i) <= k) {
                    return true;
                }
            }

            map.put(nums[i], i);
        }

        return false;
    }

    public boolean containsDuplicate(int[] nums) {

        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
        }
        return false;
    }

    public static void main6(String[] args) {
        String[] strings = new String[] {"i","love","leetcode","i","love","coding"};
        new Solution().topKFrequent(strings, 2);
        String[] strings2 = new String[] {"the","day","is","sunny","the","the","the","sunny","is","is"};
        new Solution().topKFrequent(strings2, 4);
    }

    public List<String> topKFrequent(String[] words, int k) {

        //将单词及其与数量的映射关系存入HashMap
        Map<String, Integer> hashMap = new HashMap<>();

        //没有加入过就put新元素,有就val++
        for (String word : words) {

            //存储String的value值
            int c = hashMap.getOrDefault(word, 0);
            //之前没有元素
            if (c == 0) {
                hashMap.put(word, 1);
            }
            //之前就有元素
            else {
                hashMap.put(word, c + 1);
            }
        }

        PriorityQueue<  Map.Entry<String, Integer>  > minQ =
                /**
                 * k是堆容量
                 * (k,Comparator)是优先队列的构造方法之一
                 */
                new PriorityQueue<> (k, new Comparator< Map.Entry<String, Integer> >() {
                    //或者:频率最小, 单词最大, 出堆后reverse (小根堆特性)
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        /**
                         * o1值比o2大: 根据小根堆,o2会上堆顶,但是我们需要保持o1在堆顶,即
                         * compareTo返回正数时候, 会交换
                         * 结论: o1值比o2大的时候,返回负数
                         *
                         * o1值和o2相等: 我们需要将单词小的放在上面
                         * 结论: o1单词比o2单词小时候 返回负数(不交换)
                         */
                        if (o1.getValue().compareTo(o2.getValue()) == 0) {
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue() - o2.getValue();
                    }
                });

        //计数器
        int i = 0;
        for (Map.Entry<String, Integer> mapEntry:
                hashMap.entrySet()) {
            if (i < k) {
                minQ.offer(mapEntry);
                i++;
            } else {
                //堆顶元素(最小元素)
                Map.Entry<String, Integer> top = minQ.peek();
                //堆空了 直接跳过
                if (top == null) {
                    continue;
                }
                //小堆堆顶频率< :出堆
                if (top.getValue().compareTo(mapEntry.getValue()) < 0) {
                    minQ.poll();
                    minQ.offer(mapEntry);
                }
                //堆顶频率== :比较单词
                else if (top.getValue() == mapEntry.getValue()){
                    //堆顶单词大 :出堆
                    if (top.getKey().compareTo(top.getKey()) > 0) {
                        minQ.poll();
                        minQ.offer(mapEntry);
                    }
                }
            }
        }

        List<String> list = new ArrayList<>();
        int size = minQ.size();
        for (int j = 0; j < size; j++) {
            list.add(minQ.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

    public static void main5(String[] args) {
        int[] ints = new int[] {1,2,3,2,2,2,5,4,2};
        new Solution().MoreThanHalfNum_Solution(ints);
    }

    public void MoreThanHalfNum_Solution (int[] numbers) {
         Map<Integer, Integer> map = new HashMap<>();

         int len = numbers.length;
        for (int number : numbers) {
            //有就val++ 没有就1
            if (map.containsKey(number)) {
                map.put(number, map.get(number) + 1);
            } else {
                map.put(number, 1);
            }
        }

        int nums = 0;
        //遍历map,如果V > len/2输出
        for (Map.Entry<Integer, Integer> m:
                map.entrySet()) {
            nums = m.getValue();
            if (nums > len / 2) {
                nums = m.getKey();
                break;
            }
        }
    }

    public static void main4(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();

        //false表示不是数字
        boolean flg = false;
        //stringBuilder用来拼接数字串
        StringBuilder stringBuilder = new StringBuilder();
        //ret用来存储最长数字串
        String ret = "0";

        //遍历数组找数字串
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            //之前一直是数字
            if (flg) {
                //变非数字了
                if (c < 48 || c > 57) {
                    flg = false;
                    //比之前的长就存储
                    if (stringBuilder.length() > ret.length()) {
                        ret = stringBuilder.toString();
                    }
                    //sBuilder归零
                    stringBuilder = new StringBuilder();
                }
                // 或者是最后一个数字
                else if ( i == (str.length() - 1)) {
                    stringBuilder.append(c);
                    if (stringBuilder.length() > ret.length()) {
                        ret = stringBuilder.toString();
                    }
                    //sBuilder归零
                    stringBuilder = new StringBuilder();
                }
                //还是数字:继续拼接
                else {
                    stringBuilder.append(c);
                }
            }
            //之前就是非数字
            else {
                //变数字了
                if (c >=48 && c <= 57) {
                    flg = true;
                    stringBuilder.append(c);
                }
            }
        }
        System.out.print(ret);
    }

    public static void main3(String[] args) {

        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextLine()) {

            int n = Integer.parseInt(scanner.nextLine());
            String s = scanner.nextLine();
            String[] strings = s.split(" ");

            int ret = 1;
            //默认逆序
            boolean flg = false;
            //不止一个数
            if (strings.length > 1) {
                //正序为true
                if (Long.parseLong(strings[1]) > Long.parseLong(strings[0])) {
                    flg = true;
                }

                for (int i = 1; i < strings.length; i++) {
                    //前面都是正序时候
                    if (flg) {
                        //后一个数小于前一个数
                        if (Long.parseLong(strings[i]) < Long.parseLong(strings[i - 1])) {
                            //改为逆序
                            flg = false;
                            //防止最后一个数单独为一组
                            if((i + 1) != strings.length)
                                ret++;
                        }
                    }

                    //前面都是逆序的时候
                    else {
                        //后一个数大于前一个数
                        if (Long.parseLong(strings[i]) > Long.parseLong(strings[i - 1])) {
                            //改为正序
                            flg = true;
                            //防止最后一个数单独为一组
                            if((i + 1) != strings.length)
                                ret++;
                        }
                    }
                }
                System.out.println(ret);
            }
            //只有一个数直接1
            else {
                System.out.println(strings.length);
            }
        }

    }

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] strings = s.split(" ");
        for (int i = strings.length - 1; i >= 0; i--) {
            if (i != 0) {
                System.out.print(strings[i] + " ");
            } else {
                System.out.print(strings[i]);
            }
        }
    }

    public static void main1(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String crString = new String();
        String incrString = new String();
        Set<Character> set = new HashSet<>();

        //
        crString = scanner.nextLine();
        incrString = scanner.nextLine();
        crString.toUpperCase();
        incrString.toUpperCase();

        int i = 0;
        while (i < incrString.length()) {
            if (!set.contains(incrString.charAt(i))) {
                set.add(incrString.charAt(i));
            }
            i++;
        }

        i = 0;
        while (i < crString.length()) {
            if (!set.contains(crString.charAt(i))) {
                System.out.print(crString.charAt(i));
                set.add(incrString.charAt(i));
            }
            i++;
        }

    }

    public int numJewelsInStones (String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        int ret = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) {
                ret++;
            }
        }
        return ret;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
        public Node() {}
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> hashMap = new HashMap<>();
        Node tmpNode = head;
        Node newHead = new Node(tmpNode.val);
        hashMap.put(head, newHead);
        tmpNode = tmpNode.next;
        while (tmpNode != null) {
            hashMap.put(tmpNode, new Node(tmpNode.val));
            tmpNode = tmpNode.next;
        }
        tmpNode = head;
        while (tmpNode != null) {
            hashMap.getOrDefault(tmpNode, null).next = hashMap.getOrDefault(tmpNode.next, null);
            hashMap.getOrDefault(tmpNode, null).random = hashMap.getOrDefault(tmpNode.random, null);
            tmpNode = tmpNode.next;
        }
        return newHead;
    }

    public int singleNumber1 (int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }

    public int singleNumber (int[] nums) {
        int ret = 0;
        Set<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!hashSet.contains(nums[i])) {
                hashSet.add(nums[i]);
            } else {
                hashSet.remove(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

}
